package com.cute.leetcode.editor.cn;

import java.util.Scanner;

public class HJ6ZhiShuYinZI {
    /**
     * 华为机试练习题目
     * 求出输入数字的所有素数因子，因子按照从大到小的顺序输出
     * 一个数的因子最大为该数的正平方根
     * 所以使用Math.sqrt(num)进行优化，如果超过这个范围，这个数本身就是素数了
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int k = (int) Math.sqrt(num);
        for (int i = 2; i <= k ; i++) {//从小的素数开始遍历
            while (num % i == 0){
                System.out.print(i);
                num /= i;
            }
        }
        System.out.println(num == 1 ? "" : num + " ");


        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int money = sc.nextInt();
            int m = sc.nextInt();
            sc.nextLine();
            money /= 10;
            int[][] prices = new int[m+1][3];
            int[][] weights = new int[m+1][3];
            for (int i = 1; i <= m; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                int c = sc.nextInt();
                a /= 10;//price
                b = b * a;//weight
                if (c == 0) {
                    // 主件
                    prices[i][0] = a;
                    weights[i][0] = b;
                } else if (prices[c][1] == 0) {
                    // 附件1
                    prices[c][1] = a;
                    weights[c][1] = b;
                } else {
                    // 附件2
                    prices[c][2] = a;
                    weights[c][2] = b;
                }
                sc.nextLine();
            }
            int[][] dp = new int[m+1][money+1];
            for (int i = 1; i <= m; i++) {
                for(int j = 1; j <= money; j++) {
                    int a = prices[i][0];
                    int b = weights[i][0];
                    int c = prices[i][1];
                    int d = weights[i][1];
                    int e = prices[i][2];
                    int f = weights[i][2];

                    dp[i][j] = j - a >= 0 ? Math.max(dp[i-1][j], dp[i-1][j-a] + b) : dp[i-1][j];
                    dp[i][j] = j-a-c >= 0 ? Math.max(dp[i][j], dp[i-1][j-a-c] + b + d):dp[i][j];
                    dp[i][j] = j-a-e >= 0 ? Math.max(dp[i][j], dp[i-1][j-a-e] + b + f):dp[i][j];
                    dp[i][j] = j-a-c-e >= 0 ? Math.max(dp[i][j], dp[i-1][j-a-c-e] + b +d + f):dp[i][j];
                }
            }

            System.out.println(dp[m][money] * 10);


        }

    }
}
